6940. Максимальная частота слов

Обратная частота документа (tf-idf) является числовой статистикой, которая отражает важность слова в наборе документов. Она часто используется в информационно-поисковых системах. Число раз, которое слово встречается в документе (частота слова), является одним из основных факторов для получения tf-idf.

Вам следует написать программу, которая найдет чаще всего встречаемое слово в документе.

Вход. Первая строка содержит количество слов n (1 ≤ n ≤ 1000). Следующие n строк задают список слов, по одному слову в строке. Слово содержит только латинские буквы нижнего регистра и имеет длину до 20 символов.

Выход. Вывести слово с максимальной частотой, а также через пробел саму частоту. Если существует более одного результата, выведите лексикографически наибольший.

Пример входа	Пример выхода
10 mountain lake lake zebra tree lake zebra zebra animal lakes	zebra 3

РЕШЕНИЕ

структуры данных - map

Анализ алгоритма

Объявим структуру данных map<string, int> m, в которой будем подсчитывать сколько раз встретилось каждое слово. Затем следует найти слово, которое встретилось наибольшее число раз. Если таких слов несколько, то выводим лексикографически наибольшее.

Реализация алгоритма

В отображении m подсчитаем сколько раз встретилось каждое слово.

map<string,int> m;

Читаем и подсчитываем слова.

cin >> n;

for (i = 0; i < n; i++)

{

cin >> s;

m[s]++;

}

Находим слово res, которое встречается наибольшее количество раз mx.

mx = 0;

for (auto x : m)

Если наибольшее количество раз встречаются несколько слов, то в res заносим лексикографически наибольшее.

if (x.second >= mx)

{

mx = x.second;

res = x.first;

}

Выводим слово с максимальной частотой и саму частоту.

cout << res << " " << mx << endl;

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

TreeMap<String, Integer> tree = new TreeMap<String, Integer>();

int test = con.nextInt();

while(test-- > 0)

{

String s = con.next();

tree.put(s, tree.getOrDefault(s, 0) + 1);

}

int max = -1;

String res = null;

for(String s : tree.keySet())

{

int n = tree.get(s);

if (n >= max)

{

res = s;

max = n;

}

}

System.out.println(res + " " + max);

con.close();

}

}